package edu.bupt.e1btree;

public class T21ConstructPreIn {
    public TreeNode buildTree(int[] pre, int[] in) {

        TreeNode construct = construct(pre, 0, pre.length, in, 0, in.length);
        return construct;
    }

    private TreeNode construct(int[] pre, int prestart, int preend, int[] in, int instart, int intend){
        if (prestart >= preend) return null;
        int indexInMiddle = get(in, pre[prestart]);
        int leftLen = indexInMiddle - instart + 1;
        int rightLen = intend - indexInMiddle -1;
        TreeNode treeNode = new TreeNode(pre[prestart]);
        treeNode.left = construct(pre,prestart+1,prestart+leftLen, in, instart,indexInMiddle);
        treeNode.right = construct(pre,prestart + leftLen,preend,in,indexInMiddle+1,intend);
        return treeNode;
    }

    private int get(int[] arr, int tar){
        for(int i=0;i<arr.length;i++){
            if (arr[i] == tar){
                return i;
            }
        }
        return -1;
    }
}
